class LinkNode {
  right?: LinkNode;
  left?: LinkNode;
  val: number;
  name: string;
  constructor(val: number, name: string, left?: LinkNode, right?: LinkNode) {
    this.left = left;
    this.right = right;
    this.val = val;
    this.name = name;
  }
}

class AllOne {
  keyMap: Map<string, LinkNode>;
  max?: LinkNode;
  min?: LinkNode; 
  constructor() {
    this.keyMap = new Map();
    this.max = undefined;
    this.min = undefined;
  }

  inc(key: string): void {
    let node = this.keyMap.get(key);
    if(node) {
      node.val ++;
      if(node.left) { 
        node.left.right = node.right;
      } else {
        if(node.right) {
          this.min = node.right;
        }
      }
      if(node.right) { 
        node.right.left = node.left; 
      } else {
        if(node.left) this.max = node.left;
      }
      if(!node.left && !node.right) {
        return ;
      }
      let go = node.right;
      while(go && node.val > go.val) {
        go = go.right;
      }
      if(go) {
        let temp = go.left;
        node.left = go.left;
        node.right = go;
        go.left = node;
        if(!node.left) {
          this.min = node;
        }
        if(temp) temp.right = node;
      } else {
        let temp = this.max;
        this.max = node;
        node.left = temp;
        node.right = undefined;
        if(temp) temp.right = node;
      }
    } else {
      node = new LinkNode(1, key);
      this.keyMap.set(key, node);
      if(this.min) {
        let temp = this.min;
        this.min = node;
        node.right = temp;
        if(temp) temp.left = node;
      } else {
        this.min = node;
        this.max = node;
      }
    }
  }

  dec(key: string): void {
    const node = this.keyMap.get(key);
    if(!node) return ;
    node.val --;
    if(node.left) node.left.right = node.right;
    if(node.right) {
      node.right.left = node.left;
    } else {
      if(node.left) {
        this.max = node.left;
      }
    }
    if(node.val === 0) {
      if(!node.left) {
        this.min = node.right;
      }
      this.keyMap.delete(key);
      return ;
    }
    let go = node.left;
    while(go && node.val < go.val) {
      go = go.left;
    }
    if(go) {
      let temp = go.right;
      go.right = node;
      node.left = go;
      node.right = temp;
      if(!node.right) {
        this.max = node;
      }
      if(temp) temp.left = node;
    } else {
      let temp = this.min;
      this.min = node;
      if(temp) temp.left = node;
      node.right = temp;
      node.left = undefined;
    }
    
  }

  getMaxKey(): string {
    return this.max ? this.max.name : '';
  }

  getMinKey(): string {
    return this.min ? this.min.name : '';
  }
}

function print(node?: LinkNode): void {
  let ret = '';
  if(node?.left) {
    console.log('wrong');
  }
  while(node) {
    ret += `${node.name} ${node.val} -> `
    node = node.right;
  }
  console.log(ret);
}

const obj = new AllOne();
const cmds = ["AllOne","inc","inc","inc","dec","inc","inc","getMaxKey","dec","dec","dec","getMaxKey"]
const params = [[],["hello"],["world"],["hello"],["world"],["hello"],["leet"],[],["hello"],["hello"],["hello"],[]]
for(let i = 1; i < cmds.length; i++) {
  console.log(cmds[i], params[i]);
  //@ts-ignore
  console.log(AllOne.prototype[cmds[i]].bind(obj)(...params[i]));
  print(obj.min);
  console.log(obj.max?.name, obj.min?.name);
}
/**
* Your AllOne object will be instantiated and called as such:
* var obj = new AllOne()
* obj.inc(key)
* obj.dec(key)
* var param_3 = obj.getMaxKey()
* var param_4 = obj.getMinKey()
*/